package hot;

import java.util.PriorityQueue;

public class ersan {
//    https://leetcode.cn/problems/merge-k-sorted-lists/?envType=study-plan-v2&envId=top-100-liked
    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            //创建小根堆
            PriorityQueue<ListNode> heap=new PriorityQueue<>((v1, v2)->v1.val-v2.val);//可以不用写这个 因为默认就是小根堆 如果想得到大根堆，就反着写就ok
            //分别将链表中的头节点放入小根堆里面
            for(ListNode head:lists){
                if(head!=null){
                    heap.offer(head);
                }
            }
            ListNode ret=new ListNode(-1);
            ListNode cur=ret;
            while(!heap.isEmpty()){
                ListNode t=heap.poll();
                cur.next=t;
                cur=t;
                if(t.next!=null){
                    heap.offer(t.next);
                }
            }
            return ret.next;
        }
    }



    // 法二：使用归并算法（分治思想处理）
        public ListNode mergeKLists(ListNode[] lists) {
            return mergeTmp(lists,0,lists.length-1);
        }
        public ListNode mergeTmp(ListNode[] lists,int left,int right){
            if(left==right){
                return lists[left];
            }
            if(left>right){
                return null;
            }
            int mid=(left+right)/2;
            ListNode l1=mergeTmp(lists,left,mid);
            ListNode l2=mergeTmp(lists,mid+1,right);
            return mergeTwoList(l1,l2);
        }
        public ListNode mergeTwoList(ListNode l1,ListNode l2){
            if(l1==null){
                return l2;
            }
            if(l2==null){
                return l1;
            }
            //合并两个有序链表
            ListNode newHead=new ListNode(-1);
            ListNode cur=newHead;
            while(l1!=null&&l2!=null){
                if(l1.val>l2.val){
                    cur.next=l2;
                    cur=l2;
                    l2=l2.next;
                }else{
                    cur.next=l1;
                    cur=l1;
                    l1=l1.next;
                }

            }
            if(l1!=null){
                cur.next=l1;
            }
            if(l2!=null){
                cur.next=l2;
            }
            return newHead.next;
        }
    }

